6、交换瓶子

题目 交换瓶子

image-7611bd61

思路分析

用的上次贪心的结论 最少交换数就是逆序对的数量

然后就直接归并排序模版套上去了 参考：超快速排序

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=1e4+10;
int a[N];

LL merge_sort(int q[],int l,int r)
{
    if(l>=r)
        return 0;

    int mid= l + r >> 1;
    LL res=merge_sort(q,l,mid) + merge_sort(q,mid+1,r);

    int k=0,i=l,j=mid+1,tmp[r-l+1];
    while(i<=mid && j<=r)
    {
        if(q[i]<=q[j])
            tmp[k++]=q[i++];
        else
        {
            tmp[k++]=q[j++];
            res+=mid-i+1;
        }
    }
    while(i<=mid)
        tmp[k++]=q[i++];
    while(j<=r)
        tmp[k++]=q[j++];
    for(i=l,k=0;i<=r;i++,k++)
        q[i]=tmp[k];

    return res;
}

int main()
{
  int n;
  cin>>n;
  for(int i=0;i<n;i++)
    cin>>a[i];
  cout<<merge_sort(a,0,n-1);
  return 0;
}
image-4a04220b

靠 想了半天才发现 这题不是只能相邻交换 它是可以任意交换的 所以逆序对的性质在这里不适用

不能飘啊 看到一个东西觉得眼熟就乱套性质

这题正解是 确定好正确的状态 a[0]=0 a[1]=1……

然后发现某个位置不是正确的数 就说明错位了 把这个数放到它应该放的地方去 直到这个位置上的数也放成了正确的数

image-6f319667

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e4+10;

int a[N],ans,n;

int main() {

    cin>>n;

    for(int i=1;i<=n; i++)

        scanf("%d", &a[i]);

    for(int i=1; i<=n; i++) {

        while(a[i]!=i) {

            swap(a[i], a[a[i]]);

            ++ans;

        }

    }

    cout<<ans;

    return 0;

}

同类题型

视频讲解

⬅️ 5、四平方和 🏠 00-刷题理模型 ➡️ 7、最大比例